#include <iostream>
using namespace std;


#include <map>
#include <string>
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
    //初始化1
    //std::map<std::string, std::string> m{ {"apple", "苹果"},
    //{"orange", "橙子"},
    //{"banana", "香蕉"} };
    ////std::map<std::string, std::string>::iterator it = m.begin();
    //auto mit = m.begin();

    map<string, string> m;
    // 插入
    m.insert(pair<string, string>("林冲", "豹子头"));
    m.insert(pair<string, string>("武松", "行者"));
    m.insert(pair<string, string>("宋江", "及时雨"));
    m.insert(make_pair("李逵", "黑旋风"));
    m.insert(make_pair("", "托塔天王"));

    cout << m.size() << endl;

    // key已经存在了，返回与key对应的value
    cout << m["武松"] << endl;

    // 问题：key不存在时,[]使用key和默认的value构造一个键值对
    // 往map中插入，最后返回默认value
    cout << m["史进"] << endl;

    m["史进"] = "九纹龙";

    //遍历1
    for (auto& e : m)
    {
        cout << e.first << "--->" << e.second << endl;
    }
    //遍历2
    auto it = m.begin();
    while (it != m.end())
    {
        cout << it->first << "--->" << it->second << endl;
        // it++;
        ++it;
    }
    cout << endl;

    //如果已经存在插入失败second是false
    auto ret = m.insert(make_pair("李逵", "铁牛"));


    // 注意：map中key不能修改---因为修改了key之后，并不能保证map是有序的

    //删除1
    m.erase("");
    //m.insert(make_pair("晁盖", "托塔天王"));
    m["晁盖"] = "托塔天王";
    m["晁盖"]="123";

    //删除2
    // map中的find按照红黑树的特性查找，O(logN)
    m.erase(m.find("宋江"));
    
    // 全局find：整体遍历--->O(N)
    // find(m.begin(), m.end(), make_pair("宋江", "及时雨"));
    return 0;
}






#include <vector>
#include <queue>

typedef pair<string, size_t> KV;

class Compare
{
public:
	bool operator()(const KV& left, const KV& right)
	{
		return left.second > right.second;
	}
};

vector<string> getFavFruits(const vector<string>& fruits, size_t k)
{
	map<string, size_t> m;
	// 1. 统计每个水果出现的次数
	for (auto& e : fruits)
		m[e]++;

	// 2. 找最喜欢的k中水果
	priority_queue<pair<string, size_t>, vector<pair<string, size_t>>, Compare> q;
	size_t count = 0;
	Compare com;
	for (auto& e : m)
	{
		if (count < k)
		{
			q.push(e);
			count++;
		}
		else
		{
			if (com(e, q.top()))
			{
				q.pop();
				q.push(e);
			}
		}
	}

	vector<string> ret;
	while (!q.empty())
	{
		ret.push_back(q.top().first);
		q.pop();
	}

	return ret;
}

int main()
{
	vector<string> fruits = {"apple", "orange", "pear", "apple", "apple", "orange", "grape", "watermelon", "pear", "pear",
	"strawberry", "pear", "banana", "apple", "orange", "banana"};


	vector<string> ret = getFavFruits(fruits, 5);
	for (auto& e : ret)
		cout << e << " ";
	cout << endl;
	return 0;
}